package functionalCore;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;

import beans.Aresta;
import beans.Grafo;
import beans.No;

public class AlgoritmoDijkstra {
	
	private final List<No> nos;
	private final List<Aresta> arestas;
	private Set<No> nosFixos;
	private Set<No> nosNaoFixos;
	private Map<No, No> anteriores;
	private Map<No, Integer> distancia;

	public AlgoritmoDijkstra(Grafo grafo) {
		
		this.nos = new ArrayList<No>(grafo.getNos());
		this.arestas = new ArrayList<Aresta>(grafo.getArestas());
	}

	public void executar(No fonte) {
		nosFixos = new HashSet<No>();
		nosNaoFixos = new HashSet<No>();
		distancia = new HashMap<No, Integer>();
		anteriores = new HashMap<No, No>();
		distancia.put(fonte, 0);
		nosNaoFixos.add(fonte);
		while (nosNaoFixos.size() > 0) {
			No no = getMinimo(nosNaoFixos);
			nosFixos.add(no);
			nosNaoFixos.remove(no);
			encontrarDistanciaMinima(no);
		}
	}

	private void encontrarDistanciaMinima(No no) {
		List<No> nosProximos = getVizinhos(no);
		for (No alvo : nosProximos) {
			if (getDistanciaCurta(alvo) > getDistanciaCurta(no)
					+ getDistancia(no, alvo)) {
				distancia.put(alvo, getDistanciaCurta(no)
						+ getDistancia(no, alvo));
				anteriores.put(alvo, no);
				nosNaoFixos.add(alvo);
			}
		}

	}

	private int getDistancia(No no, No alvo) {
		for (Aresta aresta : arestas) {
			if (aresta.getFonte().equals(no)
					&& aresta.getDestino().equals(alvo)) {
				return aresta.getPeso();
			}
		}
		throw new RuntimeException("Nada acontece");
	}

	private List<No> getVizinhos(No no) {
		List<No> vizinhos = new ArrayList<No>();
		for (Aresta aresta : arestas) {
			if (aresta.getFonte().equals(no)
					&& !estaFixo(aresta.getDestino())) {
				vizinhos.add(aresta.getDestino());
			}
		}
		return vizinhos;
	}

	private No getMinimo(Set<No> nos) {
		No minimo = null;
		for (No no : nos) {
			if (minimo == null) {
				minimo = no;
			} else {
				if (getDistanciaCurta(no) < getDistanciaCurta(minimo)) {
					minimo = no;
				}
			}
		}
		return minimo;
	}

	private boolean estaFixo(No no) {
		return nosFixos.contains(no);
	}

	private int getDistanciaCurta(No destino) {
		Integer d = distancia.get(destino);
		if (d == null) {
			return Integer.MAX_VALUE;
		} else {
			return d;
		}
	}

	
	public LinkedList<No> getCaminho(No alvo) {
		LinkedList<No> caminho = new LinkedList<No>();
		No aux = alvo;
		
		if (anteriores.get(aux) == null) {
			return null;
		}
		caminho.add(aux);
		while (anteriores.get(aux) != null) {
			aux = anteriores.get(aux);
			caminho.add(aux);
		}
		
		Collections.reverse(caminho);
		return caminho;
	}

}
